#include<queue>

struct MaxHeapComp
{
    bool operator()(const int& left, const int& right)
    {
        return left < right;
    }
};

struct MinHeapComp
{
    bool operator()(const int& left, const int& right)
    {
        return left > right;
    }
};

class MedianFinder
{
public:
    std::priority_queue<int, std::vector<int>, MaxHeapComp> maxHeap;
    std::priority_queue<int, std::vector<int>, MinHeapComp> minHeap;

    MedianFinder()
    {
    }

    void assign(int num)
    {
        if (maxHeap.empty()|| num <= maxHeap.top())
        {
            maxHeap.push(num);
        }else
        {
            minHeap.push(num);
        }
    }

    void adjust()
    {
        
        if (static_cast<int>(maxHeap.size())-static_cast<int>(minHeap.size()) >= 2)
        {
            int top = maxHeap.top();
            maxHeap.pop();
            minHeap.push(top);
        }
        if (static_cast<int>(minHeap.size())-static_cast<int>(maxHeap.size()) >= 2)
        {
            int top = minHeap.top();
            minHeap.pop();
            maxHeap.push(top);
        }
    }

    void addNum(int num)
    {
        assign(num);
        adjust();
    }


    double findMedian()
    {
        if (maxHeap.size() == minHeap.size())
        {
            return static_cast<double>((maxHeap.top() + minHeap.top())) / 2;
        }
        else if (maxHeap.size() > minHeap.size())
        {
            return static_cast<double>(maxHeap.top());
        }else
        {
            return static_cast<double>(minHeap.top());
        }
    }
};

